package com.sam.sort;

/**
 * 手写排序算法，练习
 * Created by samwang on
 */
public class WriteSort {

    /**
     * 交换数组中两个元素的位置
     * @param array
     * @param index1
     * @param index2
     */
    private static void exchangeElements(int[] array, int index1, int index2) {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        boolean hasChange ;
        for (int i = 0; i < arr.length; i++) {
            hasChange = false;
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j] < arr[j - 1]) {
                    exchangeElements(arr, j, j - 1);
                    hasChange = true;
                }
            }

            if (!hasChange) {
                break;
            }
        }
    }

    /**
     * 选择排序
     * @param arr
     */
    public static void selectSort(int[] arr) {
        int minIndex;
        for (int i = 0; i < arr.length; i++) {
            minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                exchangeElements(arr, i, minIndex);
            }
        }
    }


    /**
     * 插入排序
     * @param arr
     */
    public static void insertSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    exchangeElements(arr, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }


    /**
     * 希尔排序
     * @param arr
     */
    public static void shellSort(int[] arr) {
        int increase = arr.length;
        while (true) {
            increase /= 2;

            for(int k= 0;k<increase;k++) {
                for (int i = k; i < arr.length; i += increase) {
                    for (int j = i; j>k;j-=increase) {
                        if (arr[j] < arr[j - increase]) {
                            exchangeElements(arr, j, j - increase);
                        }
                    }
                }
            }

            if (increase == 1) {
                break;
            }
        }
    }

    /**
     * 快速的排序
     *
     * @param arr
     * @param l 左起始位置
     * @param r 右起始位置
     */
    public static void quickSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int i = l;
        int j = r;
        int key = arr[i];
        while (i < j) {
            while (i < j && arr[j] >= key) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
            while (i < j && arr[i] < key) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = key;

        quickSort(arr, l, i - 1);
        quickSort(arr, i + 1, r);


    }

    /**
     *         mergeSort(testData, 0, testData.length-1, new int[testData.length]);
     * @param a
     * @param first
     * @param last
     * @param temp
     */
    public static void mergeSort(int a[],int first,int last,int temp[]){
        if (first >= last) {
            return;
        }
        int middle = (first + last) / 2;
        mergeSort(a, first, middle, temp);
        mergeSort(a, middle + 1, last, temp);
        mergeArray(a, first, middle, last, temp);
    }

    //合并 ：将两个序列a[first-middle],a[middle+1-end]合并
    private static void mergeArray(int a[],int first,int middle,int end,int temp[]){
        int i = first;
        int j = middle + 1;
        int k = first;
        while (i <= middle && j <= end) {
            if (a[i] < a[j]) {
                temp[k] = a[i];
                i++;
            } else {
                temp[k] = a[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            temp[k] = a[i];
            i++;
            k++;
        }

        while (j <= end) {
            temp[k] = a[j];
            j++;
            k++;
        }

        for (int l = first; l <= end; l++) {
            a[l] = temp[l];
        }

    }


    /**
     * 堆排序
     * @param array
     */
    public static void heapSort(int[] array) {
        if (array == null || array.length == 1) {
            return;
        }

        buildMaxHeap(array);

        for (int i = array.length - 1; i > 0; i--) {
            exchangeElements(array, i, 0);
            maxHeap(array, i, 0);
        }
    }

    private static void buildMaxHeap(int[] array) {
        int half = array.length / 2 - 1;
        for (int i = half; i >= 0; i--) {
            maxHeap(array, array.length, i);
        }
    }

    private static void maxHeap(int[] array, int heapSize, int index) {
        int left = index * 2 + 1;
        int right = index * 2 + 2;
        int largest = index;
        if (left < heapSize && array[left] > array[largest]) {
            largest = left;
        }
        if (right < heapSize && array[right] > array[largest]) {
            largest = right;
        }

        if (largest != index) {
            exchangeElements(array, index, largest);
            maxHeap(array, heapSize, largest);
        }

    }

    /**
     * 基数排序
     * d表示最大的数有多少位
     *
     * 原理：最后排序最高位的，最大的当然为最大值，最小的为最小值，相等的情况在上一轮的桶排序中已经排好了。
     */
    public static void radixSort(int[] array,int d) {
        int[][] temp = new int[10][array.length];
        int[] count = new int[10];

        int m = 1;
        int n = 1;
        int k;

        while (m <= d) {
            for (int i : array) {
                k = i / n % 10;
                temp[k][count[k]] = i;
                count[k]++;
            }

            k = 0;
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < count[i]; k++, j++) {
                    array[k] = temp[i][j];
                }
                count[i] = 0;
            }

            n *= 10;
            m++;
        }

    }

}
